/*
 * @lc app=leetcode.cn id=1856 lang=typescript
 *
 * [1856] 子数组最小乘积的最大值
 */

// @lc code=start
function maxSumMinProduct(nums: number[]): bigint {
  const m = nums.length;
  const l: number[] = new Array(m).fill(-1);
  const r: number[] = new Array(m).fill(m);
  const stack: number[] = [];
  // 计算当前元素左边最近小于它的和右边最近小于它的
  for (let i = 0; i < m; i++) {
    while (stack.length && nums[i] <= nums[stack[stack.length - 1]]) {
      r[stack.pop()] = i;
    }
    if (stack.length) l[i] = stack[stack.length - 1];
    stack.push(i);
  }
  // 前缀和，方便计算区间和
  const sum: number[] = new Array(m + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    sum[i] = nums[i - 1] + sum[i - 1];
  }

  let ans: bigint = BigInt(0);
  const mod = BigInt(1e9 + 7);
  // 计算每个元素的最小乘积，取其中的最大值
  for (let i = 0; i < m; i++) {
    let total = BigInt(nums[i]) * BigInt(sum[r[i]] - sum[l[i] + 1]);
    if (total > ans) ans = total;
  }

  return ans % mod;
}
// @lc code=end
